This application relates generally to the field of hash tables. More specifically, the disclosure provided herein relates to implementing timeouts in hash table records through time-reversed linear probing.
Storing records in a data table and retrieving the records are common tasks. Various data structures, table organizations, and access techniques have been utilized to determine a location for storing a record and to determine the location of the data table in which the record has been stored. In general, each record includes a data field and an associated key. The data field contains the relevant value to be stored and searched, and the key may be any suitable identifier associated with the value. This is sometimes referred to as a key-value pair. Various techniques for organizing the data table have been developed, including hash tables.
Hash tables employ hashing functions to store, search for, and delete records based on a key within or assigned to each record. In a common implementation for inserting data into a hash table, a hashing function receives as input the key. The hashing function then outputs a storage location where the key and value are stored. Where the data table is implemented as an array, the key maps to an index of the array, and the value is stored in the associated element of the array. Approaches for searching records in the hash table may utilize the hashing function in a similar manner.
In various applications, a user may desire that each record within the hash table expires after a given amount of time. For example, the user may want to conserve storage space. The temporary lifespan of a record may be referred to as a timeout. However, current approaches for implementing timeouts are sub-optimal. For example, one approach for implementing timeouts called tumbling windows utilizes two separate hash tables. However, maintaining and searching through two separate hash tables wastes space and consumes excessive time.